COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\input macro[1,mps]
C00008 ENDMK
C⊗;
\input macro[1,mps]
\input macrwf[1,mps]
\magnification\magstephalf
\baselineskip 14pt
\leftline{\sevenrm A04.Tex[262,RWF]\today}
\leftline{\copyright\sevenrm Robert W. Floyd, September 1, 1989}
\leftline{\sevenrm Unpublished draft}
\bigskip
\noindent [Sent to Rivest in ms. form]

Let $Q(A,B)$ be the recursive partitioning step in Quicksort that
partitions the $S↓i$ for $A+2 \leq i \leq B-1$.  The range of $A$ and $B$, 
corresponding to  $1\leq i \leq N$, is $-1 \leq A$, $B \leq N+1$.  The
number partitioned is $B-A-2$; the number of comparisons is $B-A-3$.  For
$O\leq A$, $B\leq N$, $Q(A,B)$ occurs only if $S↓{A+1}$ and $S↓B$ are both
selected before any other of the $B-A = D$ quantiles $S↓{A+1}\ldots S↓B$.

The probability is
$${D\choose 2}↑{-1} = 2({1\over {D-1}}- {1\over D}).$$
The expected number of comparisons made in all $Q(A,B)$ with $O\leq A$,
$B\leq N$, is
$$\sum↓{A,D}[O\leq A, A+D\leq N, D\geq 3] 2\left({1\over D-1} - {1\over D}\right)
(D-3)$$
$$\eqalignno{&= 2 \sum↓D [3\leq D\leq N]\sum↓A [O\leq A\leq N-D]\left({3\over D}-
{2\over D-1}\right)\cr
&= 2 \sum↓D [3\leq D\leq N]\left({3 (N-D+1)\over D}- {2(N-D+1)\over D-1}\right)\cr
&= 2 \sum↓D [3\leq D\leq N]\left({3(N+1)\over - 3} - {2N\over D-1} + 2)\right)\cr
&= 2 (3 (N+1)(H↓N - H↓2) - (N-2) - 2N (H↓{N-1} - H↓1)).&(*)\cr}$$

For $A \geq 0$, $B = N+1$, $D \geq 3$, $Q(A,B)$ occurs if $S↓{A+1}$ is selected
before any other of the $D-1$ quantiles $S↓{A+1}\ldots S↓{B-1}$.  The
probability is $1\over D-1$.  The expected number of comparisons made in all
$Q(A,B)$ with $A\geq 0$, $B = N+1$ is
$$\sum↓D [3\leq D \leq N+1] {D-3\over D-1}$$
$$\eqalignno{&=\sum↓D [3 \leq D\leq N+1]\left (1 - {2\over D-1}\right)\cr
&= N-1 - 2 (H↓N- H↓1).&(**)\cr}$$
By symmetry, the same expected number of comparisons is made with $A = -1$,
$B\leq N$.

The call $Q(A,B)$ with $A = -1$, $B = N+1$ always occurs, and the number of
comparisons is
$$N-1\eqno(***)$$
Adding (*), twice (**), and (***) gives
$$2N H↓N - 4N + 2H↓N$$
as the expected number of comparisons for Quicksort.

The Find algorithm is a variant on Quicksort, seeking only $S↓M$, and 
therefore only performing $Q↓{A,B}$ if $A+2\leq M\leq B-1$.

The analysis of Find simply omits from the above sums all $Q(A,B)$ with 
$A\geq M-1$ or $B\leq M$.  However, it is just as easy to analyze a more
general situation where $S↓E$ through $S↓F$ are not required.  The
Find algorithmm is the case that $S↓1$ through $S↓{M-1}$, and $S↓{M+1}$
through $S↓N$, are not required.

First, consider the case $1 < E$, $F < N$.  We omit from the sum those
terms with $A\geq E-2 \geq 0$, $B\leq F+1\leq N$, all belonging to (+).  The
omitted part is
$$\sum↓{A,D}[E-2\leq A, A+D\leq F-1, D\geq 3] 2 \left ({1\over D-1} -
{1\over D}\right )(D-3)$$
$$\eqalign{& = 2 \sum↓D [3\leq D\leq F-E+1]\sum↓A [E-2\leq A\leq F-D-1]\left 
({3\over D} - {2\over D-1}\right )\cr
& = 2\sum↓D [3\leq D\leq F-E+1]\left ({3(F-D-E+2)\over D} -
{2(F-D-E+2)\over D-1}\right )\cr
& = 2\sum↓D [3\leq D\leq F-E+1]\left ({3(F-E+2)\over D} - {2(F-E+1)\over D-1}
-1\right )\cr
& = 2\bigl (3(F-E+2)(H↓{F-E+1} - H↓2) - 2(F-E+1)(H↓{F-E}- H↓1) 
- (F-E+1)\bigr )\cr}$$
Let $G = F-E+1$ be the number of quantiles not required; the saving is
$$2\left (3(G+1)({H↓G} - {3\over 2}) - 2G (H↓{G-1} - 1) - G\right )$$
which expands to
$$2GH↓G - 7G + GH↓G- 5$$
The case where $E=1$ or $F=N$ is left as an exercise.  When $E=1$ and $F=N$, the
number of comparisons is zero.
\bye